<?php
/**
 * Created by IntelliJ IDEA.
 * User: Administrator
 * Date: 2019/10/25
 * Time: 12:01
 */

class Solution_01
{
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function findMedianSortedArrays($nums1, $nums2) {
        $nums1_length = count($nums1);
        $nums2_length = count($nums2);
        if($nums1_length == 0 ){
            return $this->findMedianFromSortedArrays($nums2, $nums2_length);
        }
        if($nums2_length == 0 ){
            return $this->findMedianFromSortedArrays($nums1, $nums1_length);
        }
        $total = $nums1_length + $nums2_length;
        $k = intval($total/2);
        if($total % 2 == 1){
          return  $this->findMedianFromTwoSortedArrays($nums1,0,$nums2,0,$k+1);
        }
        return ($this->findMedianFromTwoSortedArrays($nums1,0,$nums2,0,$k) + $this->findMedianFromTwoSortedArrays($nums1,0,$nums2,0,$k+1))/2.0;
    }

    /**
     * 返回单个有序数组的中位数
     * @param $nums
     * @param $length
     * @return bool|float
     */
    public function findMedianFromSortedArrays($nums, $length)
    {
        if($length <1) return false;
        if($length % 2 ==0){
            return ($nums[intval($length/2)]+$nums[intval($length/2)-1])/2.0;
        }
        return $nums[intval($length/2)];
    }

    public function findMedianFromTwoSortedArrays($nums1,$nums1_start,$nums2,$nums2_start,$k)
    {
        //当$nums1_start 或 $nums2_start 超过数组长度，则第k个数为另外一个数组第k个数
        $nums1_length = count($nums1);
        $nums2_length = count($nums2);
        if($nums1_start >= $nums1_length){
            return $nums2[$nums2_start+$k-1]*1.0;
        }
        if($nums2_start >=$nums2_length){
            return $nums1[$nums1_start+$k-1]*1.0;
        }
        if($k == 1){

            return min($nums1[$nums1_start], $nums2[$nums2_start])*1.0;
        }
        $mid1 = PHP_INT_MAX;
        $mid2 = PHP_INT_MAX;
        $midk = intval($k/2);
        if($nums1_start+$midk-1 < $nums1_length){
            $mid1 = $nums1[$nums1_start + $midk- 1];
        }
        if($nums2_start+$midk-1 < $nums2_length){
            $mid2 = $nums2[$nums2_start + $midk- 1];
        }
        if($mid1 < $mid2) return $this->findMedianFromTwoSortedArrays($nums1,$nums1_start+$midk,$nums2,$nums2_start,$k-$midk);
        return $this->findMedianFromTwoSortedArrays($nums1,$nums1_start,$nums2,$nums2_start+$midk,$k-$midk);
    }
}

$solution = new Solution_01();
$num1 = [1];
$num2 = [2,3,5,6,7];
echo $solution->findMedianSortedArrays($num1,$num2);